#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 双链表节点结构定义
typedef struct DNode {
    int data;
    struct DNode * next;
    struct DNode * prior;
} DNode, * DLinkList;

// 判断双链表是否对称的函数
bool Symmetry(DLinkList L) {
    // 本算法从两头扫描循环双链表，以判断链表是否对称
    DNode * p = L->next, * q = L->prior;    // 两头工作指针
    while (p != q && q->next != p) {        // 循环跳出条件
        if (p->data == q->data) {           // 所指结点值相同则继续比较
            p = p->next; 
            q = q->prior;
        } else {
            return false;                   // 不对称，不对称
        }
    }
    return true;                            // 比较结束后返回true代表对称
}

// 创建双链表节点
DNode * createDNode(int data) {
    DNode * node = (DNode *)malloc(sizeof(DNode));
    if (node == NULL) {
        printf("内存分配失败\n");
        return NULL;
    }
    node->data = data;
    node->next = NULL;
    node->prior = NULL;
    return node;
}

// 从数组创建循环双链表
DLinkList createCyclicDoublyList(int arr[], int size) {
    if (size <= 0) return NULL;
    
    // 创建头节点
    DLinkList head = createDNode(0);  // 头节点数据域可以为任意值
    if (head == NULL) return NULL;
    
    DNode * curr = head;
    
    // 创建数据节点
    for (int i = 0; i < size; i++) {
        DNode * newNode = createDNode(arr[i]);
        if (newNode == NULL) return NULL;
        
        // 连接新节点
        curr->next = newNode;
        newNode->prior = curr;
        curr = newNode;
    }
    
    // 形成循环：最后一个节点和头节点相互连接
    curr->next = head;
    head->prior = curr;
    
    return head;
}

// 打印循环双链表（正向打印，限制打印数量防止无限循环）
void printCyclicDoublyList(DLinkList L, int maxPrint) {
    if (L == NULL) {
        printf("链表为空\n");
        return;
    }
    
    DNode * curr = L->next;  // 从第一个数据节点开始
    int count = 0;
    
    printf("正向打印: ");
    while (curr != L && count < maxPrint) {
        printf("%d ", curr->data);
        curr = curr->next;
        count++;
    }
    
    if (count == maxPrint && curr != L) {
        printf("... (限制打印)");
    }
    printf("\n");
}

// 打印循环双链表（反向打印）
void printCyclicDoublyListReverse(DLinkList L, int maxPrint) {
    if (L == NULL) {
        printf("链表为空\n");
        return;
    }
    
    DNode * curr = L->prior;  // 从最后一个数据节点开始
    int count = 0;
    
    printf("反向打印: ");
    while (curr != L && count < maxPrint) {
        printf("%d ", curr->data);
        curr = curr->prior;
        count++;
    }
    
    if (count == maxPrint && curr != L) {
        printf("... (限制打印)");
    }
    printf("\n");
}

// 释放循环双链表内存
void freeCyclicDoublyList(DLinkList L) {
    if (L == NULL) return;
    
    DNode * curr = L->next;
    
    // 先断开循环
    L->prior->next = NULL;
    L->prior = NULL;
    
    // 释放所有数据节点
    while (curr != NULL) {
        DNode * temp = curr;
        curr = curr->next;
        free(temp);
    }
    
    // 释放头节点
    free(L);
}

// 测试
int main() {
    printf("=== 循环双链表对称性测试 ===\n\n");
    
    // 测试1: 对称链表
    printf("测试1: 对称链表 [1, 2, 3, 2, 1]\n");
    int arr1[] = {1, 2, 3, 2, 1};
    DLinkList list1 = createCyclicDoublyList(arr1, 5);
    printCyclicDoublyList(list1, 10);
    printCyclicDoublyListReverse(list1, 10);
    printf("是否对称: %s\n\n", Symmetry(list1) ? "是" : "否");
    
    // 测试2: 非对称链表
    printf("测试2: 非对称链表 [1, 2, 3, 4, 5]\n");
    int arr2[] = {1, 2, 3, 4, 5};
    DLinkList list2 = createCyclicDoublyList(arr2, 5);
    printCyclicDoublyList(list2, 10);
    printCyclicDoublyListReverse(list2, 10);
    printf("是否对称: %s\n\n", Symmetry(list2) ? "是" : "否");
    
    // 测试3: 偶数个元素的对称链表
    printf("测试3: 偶数个元素的对称链表 [1, 2, 2, 1]\n");
    int arr3[] = {1, 2, 2, 1};
    DLinkList list3 = createCyclicDoublyList(arr3, 4);
    printCyclicDoublyList(list3, 10);
    printCyclicDoublyListReverse(list3, 10);
    printf("是否对称: %s\n\n", Symmetry(list3) ? "是" : "否");
    
    // 测试4: 单个元素的链表
    printf("测试4: 单个元素的链表 [5]\n");
    int arr4[] = {5};
    DLinkList list4 = createCyclicDoublyList(arr4, 1);
    printCyclicDoublyList(list4, 10);
    printCyclicDoublyListReverse(list4, 10);
    printf("是否对称: %s\n\n", Symmetry(list4) ? "是" : "否");
    
    // 测试5: 空链表（只有头节点）
    printf("测试5: 空链表\n");
    DLinkList list5 = createCyclicDoublyList(NULL, 0);
    if (list5 != NULL) {
        printCyclicDoublyList(list5, 10);
        printf("是否对称: %s\n\n", Symmetry(list5) ? "是" : "否");
    }
    
    // 释放内存
    freeCyclicDoublyList(list1);
    freeCyclicDoublyList(list2);
    freeCyclicDoublyList(list3);
    freeCyclicDoublyList(list4);
    if (list5) freeCyclicDoublyList(list5);
    
    printf("所有测试完成！\n");
    return 0;
}
